Search results for " Bounds"
showing 10 items of 291 documents
An Algebraic Derivation of Chao’s Estimator of the Number of Species in a Community Highlights the Condition Allowing Chao to Deliver Centered Estima…
2014
Anne Chao proposed a very popular, nonparametric estimator of the species richness of a community, on the basis of a limited size sampling of this community. This expression was originally derived on a statistical basis as a lower-bound estimate of the number of missing species in the sample and provides accordingly a minimal threshold for the estimation of the total species richness of the community. Hereafter, we propose an alternative, algebraic derivation of Chao’s estimator, demonstrating thereby that Chao’s formulation may also provide centered estimates (and not only a lower bound threshold), provided that the sampled communities satisfy a specific type of SAD (species abundance dist…
Online Scheduling of Task Graphs on Hybrid Platforms
2018
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous \(4\sqrt{m/k}\)-competitive online algorithm [2], where m is the number of CPUs and k the number of GPUs (\(m\ge k\)). We prove that no online algorithm can have a competitive ratio …
Model-Free Sliding-Mode-Based Detection and Estimation of Backlash in Drives With Single Encoder
2021
Backlash is a frequently encountered problem for various drives, especially those equipped with a single encoder onside of the controlled actuator. This brief proposes a sliding-mode differentiator-based estimation of unknown backlash size while measuring the actuator displacement only. Neither actuator nor load dynamics are explicitly known, while a principal second-order actuator behavior is assumed. We make use of the different perturbation dynamics distinctive for different backlash modes and an unbounded impulse-type perturbation at impact. The latter leads to transient loss of the sliding-mode and allows for detecting an isolated time instant of the backlash occurrence. The proposed m…
Time-varying Sampled-data Observer with Asynchronous Measurements
2019
International audience; In this paper a time-varying observer for a linear continuous-time plant with asynchronous sampled measurements is proposed. The observer is contextualized in the hybrid systems framework providing an elegant setting for the proposed solution. In particular some theoretical tools are provided, in terms of LMIs, certifying asymptotic stability of a certain compact set where the estimation error is zero. We consider sampled asynchronous measurements that occur at arbitrary times in a certain window with an upper and lower bound. The design procedure, that we propose for the selection of the time-varying gain, is based on a constructive algorithm that is guaranteed to f…
Alignment-free sequence comparison using absent words
2018
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not oc…
Measuring the clustering effect of BWT via RLE
2017
Abstract The Burrows–Wheeler Transform (BWT) is a reversible transformation on which are based several text compressors and many other tools used in Bioinformatics and Computational Biology. The BWT is not actually a compressor, but a transformation that performs a context-dependent permutation of the letters of the input text that often create runs of equal letters (clusters) longer than the ones in the original text, usually referred to as the “clustering effect” of BWT. In particular, from a combinatorial point of view, great attention has been given to the case in which the BWT produces the fewest number of clusters (cf. [5] , [16] , [21] , [23] ). In this paper we are concerned about t…
Block Sorting-Based Transformations on Words: Beyond the Magic BWT
2018
The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression and later results have contributed to make it a fundamental tool for the design of self-indexing compressed data structures. The Alternating Burrows-Wheeler Transform (ABWT) is a more recent transformation, studied in the context of Combinatorics on Words, that works in a similar way, using an alternating lexicographical order instead of the usual one. In this paper we study a more general class of block sorting-based transformations. The transformations in this new class prove to be interesting combinatorial tools that offer new research perspectives. In particular, we show that all the tra…
The average element order and the number of conjugacy classes of finite groups
2021
Abstract Let o ( G ) be the average order of the elements of G, where G is a finite group. We show that there is no polynomial lower bound for o ( G ) in terms of o ( N ) , where N ⊴ G , even when G is a prime-power order group and N is abelian. This gives a negative answer to a question of A. Jaikin-Zapirain.
Automorphisms of 2–dimensional right-angled Artin groups
2007
We study the outer automorphism group of a right-angled Artin group AA in the case where the defining graph A is connected and triangle-free. We give an algebraic description of Out.AA/ in terms of maximal join subgraphs in A and prove that the Tits’ alternative holds for Out.AA/. We construct an analogue of outer space for Out.AA/ and prove that it is finite dimensional, contractible, and has a proper action of Out.AA/. We show that Out.AA/ has finite virtual cohomological dimension, give upper and lower bounds on this dimension and construct a spine for outer space realizing the most general upper bound. 20F36; 20F65, 20F28
On singular integral and martingale transforms
2007
Linear equivalences of norms of vector-valued singular integral operators and vector-valued martingale transforms are studied. In particular, it is shown that the UMD(p)-constant of a Banach space X equals the norm of the real (or the imaginary) part of the Beurling-Ahlfors singular integral operator, acting on the X-valued L^p-space on the plane. Moreover, replacing equality by a linear equivalence, this is found to be the typical property of even multipliers. A corresponding result for odd multipliers and the Hilbert transform is given.